/*
 * Author: Wang Hsutung
 * Date: 2015/12/08
 * Locale: Wuhan, Hubei
 * Email: hsu[AT]whu.edu.cn
 */
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>

#define PARENT(x) ((((x) + 1) >> 1) - 1)

template <class T> void printHeap(T heap[], size_t size)
{
    size_t i = 0, j;
    while (i < size) {
        for (j = 0; j < i + 1 && i + j < size; ++j)
            std::cout << heap[i + j] << ' ';
        std::cout << "\n";
        i += j;
    }
    std::cout << "\n";
}

template <class T> void adjustUp(T heap[], size_t idx)
{
    if (idx != 0 && heap[idx] < heap[PARENT(idx)]) {
        std::swap(heap[idx], heap[PARENT(idx)]);
        adjustUp(heap, PARENT(idx));
    }
}

template <class T> void createMinHeap(T heap[], size_t size)
{
    std::cout << "原始堆状态:\n";
    printHeap(heap, size);
    for (size_t i = 1; i < size; ++i) {
        adjustUp(heap, i);
        std::cout << "第" << i << "次调整后...\n";
        printHeap(heap, size);
    }
}

int main(int argc, char *argv[])
{
    int arrsize = 12, randmax = 200;
    int *arr = new int[arrsize];

    /* 用随机数初始化数组 */
    std::srand(std::time(NULL));
    for (int i = 0; i < arrsize; ++i)
        arr[i] = std::rand() % (randmax + 1);

    std::cout << "\n这是创建最小堆的" << arrsize << "个随机数:";
    for (int i = 0; i < arrsize ; ++i)
        std::cout << " " << arr[i];
    std::cout << "\n";

    createMinHeap(arr, arrsize);

    std::cout << "\n(#)最小堆创建后数组变为:";
    for (int i = 0; i < arrsize; ++i)
        std::cout << " " << arr[i];

    std::cout << "\n";
    delete [] arr;
    std::exit(EXIT_SUCCESS);
}

